1998-2000: Black Maria dan Ali Bakar

Selama Black Maria berada di bawah seliaan Ali Bakar, mereka diberi kelebihan untuk berlatih di studio milik beliau tetapi mereka langsung tidak mendapat sebarang tawaran persembahan. Walau bagaimanapun, Ali Bakar sememangnya mempunyai perancangan untuk berjumpa wakil-wakil daripada syarikat rakaman muzik yang terkenal pada waktu itu seperti BMG, Sony Music Malaysia dan Warner Music Malaysia, tetapi beliau sangat sibuk dengan penganjuran pelbagai konsert dan acara muzik yang lain.

Setelah dua tahun berlalu tanpa menerima sebarang tawaran persembahan dan juga tiada perancangan daripada pihak Ali Bakar untuk menghasilkan album, Sharif mengambil keputusan untuk menarik diri daripada kumpulan tersebut. Disebabkan Black Maria belum pernah menandatangani sebarang perjanjian hitam putih bersama Ali Bakar dan pihak Boxoffice Malaysia, OP meminta izin daripada Ali Bakar untuk bergerak sendiri.

Selepas Black Maria mengundurkan diri daripada seliaan Ali Bakar, Ronnie, OP dan CD meneruskan rutin latihan mereka di studio lain. Dalam masa yang sama, mereka juga mengumpul idea untuk lagu-lagu baru. OP juga bertindak proaktif dengan membawa beberapa buah lagu demo yang dirakamkan Black Maria dalam tempoh dua tahun yang lalu ke pejabat Warner Music Malaysia. Setelah mendengar kesemua rakaman lagu demo tersebut, pihak Warner Music Malaysia sangat berminat terhadap konsep lagu-lagu Black Maria dan mereka terus menawarkan peluang kepada Black Maria untuk merakamkan sebuah album penuh di bawah seliaan Garang Records.

Mereka bertiga kemudiannya mencari pemain bass baru untuk menggantikan tempat Sharif. OP berpendapat bahawa salah seorang sahabat beliau, PE (Mohd Shafiie Arshad), lebih sesuai memikul tanggungjawab sebagai pemain bass yang baru. Pada masa yang sama juga, CD mencadangkan salah seorang sahabat beliau yang merupakan seorang pemain gitar untuk mengisi tempat pemain bass. Ketika proses pemilihan tersebut, perselisihan faham berlaku antara OP dan CD. OP yang merupakan ketua kumpulan Black Maria akhirnya membuat keputusan untuk menggugurkan CD daripada Black Maria. Tempat CD kemudiannya digantikan oleh JJ (Saiful Razil Kamarudin, adik kepada Lola XPDC), seorang pemain dram sepenuh masa yang telah lama berada dalam arena muzik kelab malam.

Dengan kehadiran PE dan JJ, Black Maria terus mengorak langkah untuk melaksanakan perancangan penghasilan album sulung mereka. Ronnie dan OP bekerjasama dalam penghasilan lagu dan penulisan lirik untuk hampir kesemua lagu yang bakal dimasukkan dalam album tersebut. Walau bagaimanapun, Ronnie tidak dapat menyumbangkan suara untuk album tersebut atas faktor kesihatan yang kurang baik.

Tanpa membuang masa, mereka terus mengadakan uji bakat untuk mencari penyanyi baru untuk album tersebut. Setelah selesai proses ujibakat tersebut, akhirnya seorang anak muda yang berasal dari Kolapis Darat, Beluran, Sabah, iaitu Aziz atau nama komersialnya AG, dipilih untuk menggantikan tempat Ronnie sebagai penyanyi.

2000-2002: Kelahiran album 'Veto'; Black Maria mula dikenali ramai

Genre nu metal atau new age metal mula muncul di persada muzik dunia bermula awal tahun 1990-an dengan kemunculan pelbagai kumpulan muzik terkenal seperti Korn, Soulfly, Limp Bizkit, Rage Against The Machine, Papa Roach, Stuck Mojo, Machine Head, Linkin Park, POD, Deftones, Factory 81, Professional Murder Music, Apartment 26 dan sebagainya. Di Malaysia, genre tersebut mula bertapak dalam persada muzik arus perdana pada akhir tahun 1990-an sehingga era 2000-an. Antara kumpulan muzik tanah air yang menjadi perintis utama kepada pengaruh dan perkembangan genre ini di Malaysia ialah Black Maria sendiri, selain Dr Kronik, Sevenwords (kumpulan yang pernah dianggotai oleh Pekin Ibrahim, banyak dipengaruhi POD dan Deftones) dan Trimatra.

Untuk album sulung kumpulan Black Maria di bawah Garang Records dan Warner Music Malaysia, mereka menggunakan nama Veto sebagai judul album kerana lagu Veto merupakan lagu pertama yang dihantar oleh OP kepada Warner Music Malaysia. Pada masa itu, album demo Black Maria masih belum siap sepenuhnya. Setelah selesai proses rakaman album, Garang Records dan Warner Music Malaysia terus giat mempromosikan album tersebut di semua cabang media massa pada ketika itu - stesen radio, stesen televisyen, akhbar, majalah hiburan - melalui pengagihan salinan promosi (promo copy) album Veto. Salinan promosi tersebut dikeluarkan dalam dua jenis - ada yang mempunyai sebuah lagu sahaja iaitu lagu Veto[1], manakala sebuah lagi salinan promosi memuatkan dua buah lagu iaitu lagu Karma ... Safil??? dan Permata 20[2].

Lagu Veto mendapat sambutan yang luar biasa dalam kalangan pendengar radio pada ketika itu sehingga lagu tersebut berjaya menjadi antara juara mingguan untuk rancangan Carta ERA kendalian Halim Othman di Radio ERA selama tiga minggu berturut-turut, bermula dari 3 September 2000 hingga 17 September 2000. Video muzik lagu tersebut juga disiarkan secara kerap di kaca televisyen dan mendapat perhatian orang ramai kerana konsepnya yang dianggap canggih dan futuristik, seiring dengan perkembangan teknologi maklumat pada masa itu.